﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    //有前序和中序可以唯一确定一颗二叉树
    //有后序和中序可以唯一确定一颗二叉树
    //没有中序遍历无法确定左右部分，所以有前序和后序不能唯一确定一颗二叉树
    class ConstructTree
    {
        //==================================力扣106 从中序与后序遍历序列构造二叉树
        //根据一棵树的中序遍历与后序遍历构造二叉树
        //可以假设树中没有重复元素
        public TreeNode BuildTree(int[] inorder, int[] postorder)
        {
            //第一步，如果数组大小为0，说明是空节点了
            if (postorder.Length == 0)
                return null;

            //第二步，如果不为空，那么取后序数组的最后一个元素作为节点元素
            int rootValue = postorder[postorder.Length - 1];
            TreeNode root = new TreeNode(rootValue);

            if (postorder.Length == 1)
                return root;

            //第三步，找到后序元素的最后一个元素在中序数组的位置，作为切割点
            int delimiterIndex;
            for (delimiterIndex = 0; delimiterIndex < inorder.Length; delimiterIndex++)
            {
                if (inorder[delimiterIndex] == rootValue)
                    break;
            }

            //第四步，切割中序数组，得到中序左数组和中序右数组
            int[] middleLeft = new int[delimiterIndex];
            int[] middleRight = new int[inorder.Length - delimiterIndex - 1];
            Array.Copy(inorder, 0, middleLeft, 0, middleLeft.Length);
            Array.Copy(inorder, delimiterIndex + 1, middleRight, 0, middleRight.Length);

            //第五步，切割后序数组，得到后序左数组和后序右数组
            int[] PostLeft = new int[middleLeft.Length];//后序左数组和中序左数组长度必然一样
            int[] PostRight = new int[middleRight.Length];
            Array.Copy(postorder, 0, PostLeft, 0, middleLeft.Length);
            Array.Copy(postorder, PostLeft.Length, PostRight, 0, middleRight.Length);

            //第六步，递归处理左区间和右区间
            root.left = BuildTree(middleLeft, PostLeft);
            root.right = BuildTree(middleRight, PostRight);
            return root;
        }

        //===============================================力扣106 从前序和中序遍历序列构造二叉树
        //给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
        public TreeNode BuildeTree_2(int[] preorder, int[] inorder)
        {
            //第一步，如果数组大小为0，说明是空节点了
            if (preorder == null||preorder.Length ==0)
                return null;

            //第二步：如果不为空，那么取前序数组第一个元素作为节点元素。
            int rootValue = preorder[0];
            TreeNode root = new TreeNode(rootValue);

            if (preorder.Length == 1)
                return root;

            //第三步：找到前序数组第一个元素在中序数组的位置，作为切割点
            int delimiterIndex;
            for (delimiterIndex = 0; delimiterIndex < inorder.Length; delimiterIndex++)
            {
                if (inorder[delimiterIndex] == rootValue)
                    break;
            }

            //第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
            int[] middleLeft = new int[delimiterIndex];
            int[] middleRight = new int[inorder.Length - delimiterIndex - 1];
            Array.Copy(inorder, 0, middleLeft, 0, middleLeft.Length);
            Array.Copy(inorder, delimiterIndex + 1, middleRight, 0, middleRight.Length);

            //第五步：切割前序数组，切成前序左数组和前序右数组
            int[] PreLeft = new int[middleLeft.Length];//前序左数组和中序左数组长度必然一样
            int[] PreRight = new int[middleRight.Length];
            Array.Copy(preorder, 1, PreLeft, 0, middleLeft.Length);
            Array.Copy(preorder, PreLeft.Length+1, PreRight, 0, middleRight.Length);

            //第六步：递归处理左区间和右区间
            root.left = BuildeTree_2(PreLeft, middleLeft);
            root.right = BuildeTree_2(PreRight, middleRight);

            return root;

        }


        //============================================力扣654 最大二叉树
        //给定一个不含重复元素的整数数组nums,递归构建一个最大二叉树
        //最大二叉树：1、二叉树的跟是数组nums的最大元素
        //           2、左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树
        //           3、右子树是通过数组中 最大值右边部分 递归构造处的最大二叉树
        //数组元素>=0
        //如[3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
        public TreeNode ConstructMaxImumBinaryTree(int[] nums)
        {//思路：一般采用前序遍历，因为先构造中间节点，然后递归构造左子树和右子树

            TreeNode node = new TreeNode(0);
            if (nums.Length == 0)
            {//当传入数组大小为1时，说明遍历到叶子节点
                node.val = nums[0];
                return node;
            }

            //找到数组最大值和最大值所在的位置
            int maxVal = 0;
            int maxValIndex = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] > maxVal)
                {
                    maxVal = nums[i];
                    maxValIndex = i;
                }
            }
            node.val = maxVal;

            if (maxValIndex > 0)
            {//左边至少有一个元素才构造左子树
                int[] leftNums = new int[maxValIndex];
                Array.Copy(nums, leftNums, leftNums.Length);
                node.left = ConstructMaxImumBinaryTree(leftNums);
            }
            if(maxValIndex < nums.Length - 1)
            {//右边至少有一个元素才构造右子树
                int[] RightNums = new int[nums.Length - maxValIndex-1];
                Array.Copy(nums, maxValIndex + 1, RightNums, 0, RightNums.Length);
                node.right = ConstructMaxImumBinaryTree(RightNums);
            }
            return node;
        }
        public TreeNode ConstructMaxImumBinaryTree_2(int[] nums)
        {

            return TravelTree(nums, 0, nums.Length);
        }
        private TreeNode TravelTree(int[] nums,int left,int right)
        {//使用原数组 减少开销
           //数组左闭右开
            if (left >= right)
                return null;

            int maxValIndex = left;
            for(int i = left+1;i<right;i++)
            {
                if(nums[i] > nums[maxValIndex])
                {
                    maxValIndex = i;
                }
            }

            TreeNode node = new TreeNode(nums[maxValIndex]);

            //左闭右开：[left,maxValIndex)
            node.left = TravelTree(nums, left, maxValIndex );
            //左闭右开：[maxValIndex + 1,right)
            node.right = TravelTree(nums, maxValIndex + 1, right);
            return node;
        }

        //====================================================力扣617 合并二叉树
        //给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
        //你需要将它们合并成一个新的二叉树。合并规则是如果两个节点重叠，那么将它们的值相加作为节点合并后的新值，否则不为null的节点将直接作为新二叉树的节点
        public TreeNode MergeTrees(TreeNode root1, TreeNode root2)
        {//递归

            if (root1 == null)
                return root2;//如果root1为空，合并后就应该是t2
            if (root2 == null)
                return root1;//如果root2为空，合并后就应该是t1

            root1.val += root2.val;//中
            root1.left = MergeTrees(root1.left, root2.left);//左
            root1.right = MergeTrees(root1.right, root2.right);//右
            return root1;
        }

        public TreeNode MergeTrees_2(TreeNode root1, TreeNode root2)
        {//迭代
            if (root1 == null)
                return root2;
            if (root2 == null)
                return root1;

            Queue<TreeNode> que = new Queue<TreeNode>();
            que.Enqueue(root1);
            que.Enqueue(root2);
            while(que.Count > 0)
            {
                TreeNode node1 = que.Dequeue();
                TreeNode node2 = que.Dequeue();
                //此时两个节点一定不为空
                node1.val += node2.val;

                // 如果两棵树左节点都不为空，加入队列
                if (node1.left != null && node2.left != null)
                {
                    que.Enqueue(node1.left);
                    que.Enqueue(node2.left);
                }

                // 如果两棵树右节点都不为空，加入队列
                if (node1.right != null && node2.right != null)
                {
                    que.Enqueue(node1.right);
                    que.Enqueue(node2.right);
                }

                // 当t1的左节点 为空 t2左节点不为空，就赋值过去
                if (node1.left == null && node2.left != null)
                {
                    node1.left = node2.left;
                }
                // 当t1的右节点 为空 t2右节点不为空，就赋值过去
                if (node1.right == null && node2.right != null)
                {
                    node1.right = node2.right;
                }
            }
            return root1;
        }

        //=========================================================力扣701 二叉搜索树中的插入操作
        //给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树，返回插入后的根节点
        //输入数据保证，新值和原始二叉树中的任意节点值不同
        //这种算法不需要重构二叉树，增加的节点始终是叶子节点
        public TreeNode InsertIntoBST(TreeNode root, int val)
        {//递归
            
            if(root == null)
            {
                TreeNode node = new TreeNode(val);
                return node;
            }

            if (root.val > val)
                root.left = InsertIntoBST(root.left, val);
            if (root.val < val)
                root.right = InsertIntoBST(root.right, val);
            return root;
        }
        //----------------------------------------------------
        public TreeNode InsertIntoBST_2(TreeNode root, int val)
        {//迭代法
            TreeNode node = new TreeNode(val);
            if (root == null)
            {
                return node;
            }
            TreeNode cur = root;
            TreeNode parent = root;// 这个很重要，需要记录上一个节点，否则无法赋值新节点
            while (cur != null)
            {
                parent = cur;
                if (cur.val > val)
                    cur = cur.left;
                else
                    cur = cur.right;
            }
            //循环到底了
            if (val < parent.val)// 此时是用parent节点的进行赋值
                parent.left = node;
            else
                parent.right = node;
            return root;
        }

        //=====================================================力扣450 删除二叉搜索树中的节点
        //给定一个二叉搜索树的根节点root和一个值key，删除二叉搜索树中key对应的值，并保证二叉搜索树的性质不变
        //要求算法复杂度为O(h),h为树的高度
        //一般来说，删除节点有两个步骤：1.找到需要删除的节点。2.删除它
        public TreeNode DeleteNode(TreeNode root, int key)
        {//递归
            if (root == null)//第一种情况：没找到删除的节点，遍历到空节点直接返回了
                return root;

            if(root.val == key)
            {
                //第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回null为根节点
                //第三种情况：左孩子为空右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
                if (root.left == null)
                    return root.right;
                //第四种情况：右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
                else if (root.right == null)
                    return root.left;
                //第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子位置
                //并返回删除节点的右孩子为新的节点
                else
                {
                    //找到右子树最左边的节点
                    TreeNode cur = root.right;
                    while(cur.left != null)
                    {
                        cur = cur.left;
                    }

                    cur.left = root.left;//把要删除的节点（root)左子树放到cur的左孩子位置
                    root = root.right;//返回旧root的右孩子作为新root
                    return root;
                }
            }

            if (root.val > key)
                root.left = DeleteNode(root.left, key);
            if (root.val < key)
                root.right = DeleteNode(root.right, key);
            return root;
        }
        //--------------------------------------------------------
        public TreeNode DeleteNode_2(TreeNode root, int key)
        {//普通二叉树的删除方式  遍历整棵树
            if (root == null)
                return root;
            if(root.val == key)
            {
                if (root.right == null)// 这里第二次操作目标值：最终删除的作用
                    return root.left;

                TreeNode cur = root.right;
                while (cur.left != null)
                    cur = cur.left;
                // 这里第一次操作目标值：交换目标值其右子树最左面节点。
                int tmp = root.val;
                root.val = cur.val;
                cur.val = tmp;
            }

            root.left = DeleteNode_2(root.left, key);
            root.right = DeleteNode_2(root.right, key);
            return root;
        }

        //===============================================力扣669 修剪二叉搜索树
        //给定二傻搜索树的根节点root，同时给定最小边界low和最大边界high.通过修剪二叉搜索树，使得所有节点的值在[low,high]中
        //修剪树不应改变树中元素的相对结构（即，如果没有被移除，原有父子关系应保留），可以证明，存在唯一答案
        //所有结果应返还修剪好的新的根节点
        public TreeNode TrimBST(TreeNode root, int low, int high)
        {//递归法
            if (root == null)
                return root;

            if(root.val < low)
            {//如果当前节点元素小于low的数值，应该递归右子树，并返回右子树符合条件的头结点
                TreeNode right = TrimBST(root.right, low, high);//寻找符合区间[low, high]的节点
                return right;
            }
            if(root.val > high)
            {//如果当前节点元素大于high的数值，应该递归左子树，并返回左子树符合条件的头结点
                TreeNode left = TrimBST(root.left, low, high);
                return left;
            }

            //将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。
            root.left = TrimBST(root.left, low, high);
            root.right = TrimBST(root.right, low, high);
            return root;
        }
        public TreeNode TrimBST_2(TreeNode root, int low, int high)
        {//迭代法

            if (root == null)
                return null;

            // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
            while (root != null && (root.val < low || root.val > high))
            {
                if (root.val < low)
                    root = root.right;//小于low往右走；
                else
                    root = root.left;//大于high往左走
            }

            TreeNode cur = root;
            //root已经在[low,high]中，处理左孩子小于low的情况
            while(cur != null)
            {
                while (cur.left != null && cur.left.val < low)
                    cur.left = cur.left.right;
                cur = cur.left;
            }
            //root已经在[low,high]中，处理右孩子大于high的情况
            cur = root;
            while(cur != null)
            {
                while (cur.right != null && cur.right.val > high)
                    cur.right = cur.right.left;
                cur = cur.right;
            }
            return root;
        }

        //===================================================力扣108 将有序数组转换为二叉搜索树
        //给你一个整数数组nums,其中元素已经按照升序排序，请你将其转换为一颗高度平衡二叉搜索树
        //高度平衡：二叉树满足每个节点的左右两个子树的高度差的绝对值不超过1
        public TreeNode SortedArrayToBST(int[] nums)
        {//递归法
            TreeNode root = Travesal(nums, 0, nums.Length - 1);
            return root;
        }
        private TreeNode Travesal(int[] nums, int left, int right)
        {
            if (left > right)
                return null;
            //取中间位置
            int mid = left + ((right - left) / 2);//防止越界

            TreeNode root = new TreeNode(nums[mid]);
            root.left = Travesal(nums, left, mid - 1);
            root.right = Travesal(nums, mid + 1, right);
            return root;
        }
        //----------------------------------------------------
        public TreeNode SortedArrayToBST_2(int[] nums)
        {//迭代法

            if (nums.Length == 0)
                return null;
            TreeNode root = new TreeNode(0);//初始根节点
            Queue<TreeNode> nodeQue = new Queue<TreeNode>();//放遍历的节点
            Queue<int> leftQue = new Queue<int>();//保存左区间下标
            Queue<int> rightQue = new Queue<int>();//保存右区间下标

            nodeQue.Enqueue(root);// 根节点入队列
            leftQue.Enqueue(0);// 0为左区间初始位置
            rightQue.Enqueue(nums.Length - 1);// nums.size() - 1为右区间初始位置

            while (nodeQue.Count> 0)
            {
                TreeNode curNode = nodeQue.Dequeue();
                int left = leftQue.Dequeue();
                int right = rightQue.Dequeue();
                int mid = left + ((right - left) / 2);

                curNode.val = nums[mid];// 将mid对应的元素给中间节点

                if (left <= mid - 1)
                {// 处理左区间
                    curNode.left = new TreeNode(0);
                    nodeQue.Enqueue(curNode.left);
                    leftQue.Enqueue(left);
                    rightQue.Enqueue(mid - 1);
                }
                if(right >= mid + 1)
                {// 处理右区间
                    curNode.right = new TreeNode(0);
                    nodeQue.Enqueue(curNode.right);
                    leftQue.Enqueue(mid + 1);
                    rightQue.Enqueue(right);
                }
            }
            return root;
        }

        //=========================================================力扣538 把二叉搜索树转换为累加树
        //给出二叉搜索树的根节点，该树的节点值各不同，请你将其转换为累加树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
        int pre;
        public TreeNode ConvertBST(TreeNode root)
        {//顺序：右中左，即是反中序遍历
            pre = 0;
            Traversal(root);
            return root;
        }
        void Traversal(TreeNode cur)
        {
            if (cur == null)
                return;
            Traversal(cur.right);
            cur.val += pre; ;
            pre = cur.val;
            Traversal(cur.left);
        }

        public TreeNode ConvertBST_2(TreeNode root)
        {
            pre = 0;
            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode cur = root;
            while(cur != null || st.Count > 0)
            {
                if(cur != null)
                {
                    st.Push(cur);
                    cur = cur.right;//右
                }
                else
                {
                    cur = st.Pop();//中
                    cur.val += pre;
                    pre = cur.val;
                    cur = cur.left;//左
                }
            }
            return root;
        }

    }
}
